package j2024.j202412;

import java.util.ArrayList;
import java.util.Arrays;

public class j1212 {
    /**
     * 56. 合并区间
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
     * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            return a[0] - b[0];
        });
        int left = intervals[0][0], right = intervals[0][1];
        int n = intervals.length;
        ArrayList<int[]> ret = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            int l = intervals[i][0], r = intervals[i][1];
            if(right>=l){
                right = Math.max(r,right);
            }else {
                ret.add(new int[]{left,right});
                left = l;right = r;
            }
        }
        ret.add(new int[]{left,right});
        return ret.toArray(new int[ret.size()][]);
    }


    /**
     * 189. 轮转数组
     * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
     *
     *
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] ret = new int[n];
        for (int i = 0; i < n; i++) {
            ret[(i+k)%n] = nums[i];
        }
        System.arraycopy(ret, 0, nums, 0, n);
    }


    /**
     * 238. 除自身以外数组的乘积
     * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
     *
     * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
     *
     * 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
     *
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] ret = new int[n];
        left[0] = 1;right[n-1] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i-1] * nums[i-1];
        }
        for (int i = n-2; i >=0 ; i--) {
            right[i] = right[i+1] * nums[i+1];
        }
        for (int i = 0; i < n; i++) {
            ret[i] = left[i] * right[i];
        }
        return ret;
    }
}
